package cn.fansunion.leecode.array.max;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 3. 无重复字符的最长子串 <br/>
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。<br/>
 * <br/>
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 
 * @author wen.lei@brgroup.com
 *
 *         2021-12-28
 */
public class LongestSubstringWithoutRepeatingCharacters {

    // 输入: s = "abcabcbb"
    // 输出: 3
    // 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
    // abcade

    // TODO 很多网友的算法，可读性太差了，不好理解；官网的还可以，就是优化一层循环?
    // 已经尝试了各种数据结构，性能差距有的
    public int lengthOfLongestSubstringFaster(String s) {
        return 0;
    }

    // 不用ArrayList，LinkedList，维护索引
    // 8 ms, 在所有 Java 提交中击败了22.98%的用户
    public int lengthOfLongestSubstring(String s) {
        int currentMaxSum = 0;
        final char[] charArray = s.toCharArray();
        int startIndex = 0;
        int endIndex = 0;
        String currentStr;
        for (int index = 0; index < charArray.length;) {
            char c = s.charAt(index);
            // 无重复字符，中断了
            currentStr = s.substring(startIndex, endIndex);
            //这里 index 没有++，下方index++，但是可能多走了外层for循环？
            if (currentStr.contains(String.valueOf(c))) {
                startIndex++;
            } else {
                index++;
                currentMaxSum = Math.max(currentMaxSum, endIndex - startIndex + 1);
                endIndex++;
            }
        }
        return currentMaxSum;
    }

    // 19 ms,在所有 Java 提交中击败了15.53%的用户
    // LinkedList
    public int lengthOfLongestSubstring2(String s) {
        int currentMaxSum = 0;
        LinkedList<Character> currentMaxSumList = new LinkedList<>();
        final char[] charArray = s.toCharArray();
        for (int index = 0; index < charArray.length;) {
            char c = s.charAt(index);
            // 无重复字符，中断了
            if (currentMaxSumList.contains(c)) {
                currentMaxSumList.removeFirst();
            } else {
                currentMaxSumList.add(c);
                index++;
                currentMaxSum = Math.max(currentMaxSum, currentMaxSumList.size());
            }
        }
        return currentMaxSum;
    }

    /**
     * 解题思路：一次滚动1格，满足条件，才进行到下一格。耗时：2609 ms，超出预期
     * 
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring3(String s) {
        int currentMaxSum = 0;
        List<Character> currentMaxSumList = new ArrayList<>();
        for (int index = 0; index < s.toCharArray().length;) {
            char c = s.charAt(index);
            // 无重复字符，中断了
            if (currentMaxSumList.contains(c)) {
                currentMaxSumList.remove(0);
            } else {
                currentMaxSumList.add(c);
                index++;
                currentMaxSum = Math.max(currentMaxSum, currentMaxSumList.size());
            }
        }
        return currentMaxSum;
    }

    /**
     * 之前的错误解法：clear，remove(0)都不行；<br/>
     * 以为和LongestContinuousIncreasingSubsequence、MaxConsecutiveOnes思路一致<br/>
     * 实际区别还是有的，代码结构比较像<br/>
     * 
     * @param s
     * @return
     */
    public int lengthOfLongestSubstringError(String s) {
        int currentMaxSum = 0;
        List<Character> currentMaxSumList = new ArrayList<>();
        for (char c : s.toCharArray()) {
            // 无重复字符，中断了
            if (currentMaxSumList.contains(c)) {
                currentMaxSum = Math.max(currentMaxSum, currentMaxSumList.size());
                // 第1次错误解法：currentMaxSumList.clear()
                currentMaxSumList.remove(0);
                // 和同类型题目，需要把当前字符再放进集合里
                currentMaxSumList.add(c);
            } else {
                currentMaxSumList.add(c);
            }
        }
        return Math.max(currentMaxSum, currentMaxSumList.size());
    }
}
